//
// Description: 329. 矩阵中的最长递增路径
// Created by Loading on 2022/6/18.
//

#include <bits/stdc++.h>

using namespace std;

int longestIncreasingPath(vector<vector<int>> &matrix) {
    int m = matrix.size();
    int n = matrix[0].size();

    // dist[i][j] 表示从 (i,j) 点出发的最长递增路径
    int dist[200][200];
    // 初始化
    memset(dist, -1, sizeof dist);

    // 四个方向移动数组
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    function<int(int, int)> dfs = [&](int x, int y) {
        /* 记忆化搜索 */
        if (dist[x][y] != -1) {
            return dist[x][y];
        }
        dist[x][y] = 1;
        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < m && b >= 0 && b < n && matrix[x][y] < matrix[a][b]) {
                // 四个方向，选择最大的
                dist[x][y] = max(dist[x][y], dfs(a, b) + 1);
            }
        }

        return dist[x][y];
    };

    int res = 1;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            res = max(res, dfs(i, j));
        }
    }

    return res;
}

int main() {
    vector<vector<int>> matrix = {{9, 9, 4},
                                  {6, 6, 8},
                                  {2, 1, 1}};

    auto res = longestIncreasingPath(matrix);

    cout << res << endl;

    return 0;
}